
package leetcode.leetcode_2438;
import java.util.ArrayList;

class Solution {
    private ArrayList<Integer> list;
    private int mod = (int)1e9+7;
    private long[] pow;

    public int[] productQueries(int n, int[][] queries) {
        list = new ArrayList<>();
        getList(n);
        int[] ans = new int[queries.length];
        getPow();

        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];

            // 使用快速幂计算2的幂次方并取模
            if (left == 0) {
                ans[i] = (int) pow2Mod(pow[right]);
            } else {
                ans[i] = (int) pow2Mod(pow[right] - pow[left-1]);
            }
        }
        return ans;
    }

    // 快速幂算法计算 (2^exp) % mod
    private long pow2Mod(long exp) {
        long result = 1;
        long base = 2;
        long exponent = exp;

        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exponent /= 2;
        }
        return result;
    }

    public void getList(int n) {
        ArrayList<Integer> list_temp = new ArrayList<>();
        while (n > 0) {
            list_temp.add(n % 2);
            System.out.println( n%2);
            n = n / 2;
        }
        int len = list_temp.size();
        for (int i = 0 ; i < len; i++) {
            if (list_temp.get(i) == 1) {
               list.add(i);
            }
        }
    }

    void getPow() {
        pow = new long[list.size()];
        pow[0] = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            pow[i] = pow[i-1] + list.get(i);
        }
    }

    public static void main(String[] args) {
        int n = 14;
        int[][] queries = {{0,1},{2,3},{1,2}};
        System.out.println(new Solution().productQueries(n, queries));
    }
}
